import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-12-21
 * Time: 11:32
 */

public class TestHash {

    /**
     * 两数之和（思路：使用hash表，找差值，但是对于存在多组结果的情况并且元素可重复，这种方法就不太适用了）
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum (int[] numbers, int target) {
        // 创建结果数组
        int[] res = new int[2];
        // 解题思路：找差集在hashMap中是否存在
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i ++) {
            int sub = target - numbers[i];
            if (!map.containsKey(sub)) {
                // 如果map不存在差值，则将nums[i]插入到map中
                map.put(numbers[i],i+1);
            } else {
                // map中存在sub，则说明找到了
                // map中已存在的一定是int[0]
                res[0] = map.get(sub);
                res[1] = i + 1;
            }
        }
        return res;
    }

    /**
     * 超过一半的数字
     * @param numbers
     * @return
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // 思路：遍历数组，使用hash表，遇到重复元素value+1，返回长度超过一半的元素
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i ++) {
            if (!map.containsKey(numbers[i])) {
                // map中不存在，则加入
                map.put(numbers[i], 1);
            } else {
                // map中存在，则value+1
                map.put(numbers[i], map.get(numbers[i]) + 1);
            }
            // 判断是否超过一半
            if (map.get(numbers[i]) > numbers.length / 2) {
                res = numbers[i];
                break;
            }
        }
        return res;
    }

    /**
     * 找到只出现一次的两个数字
     * @param nums
     * @return
     */
    public int[] FindNumsAppearOnce (int[] nums) {
        // 定义结果集
        int[] res = new int[2];

        // 定义存储计数的map；O(N)
        Map<Integer,Integer> map = new HashMap<>();
        // 计数O(N)
        for (int i = 0; i < nums.length; i ++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i],1);
            } else {
                map.put(nums[i],map.get(nums[i])+1);
            }
        }
        // 找到唯一的元素
        int i = 0;
        for (Map.Entry<Integer,Integer> set:map.entrySet()) {
            int val = set.getValue();
            if (val == 1) {
                res[i++] = set.getKey();
            }
            if (i == 2) {
                break;
            }
        }
        if (res[0] > res[1]) {
            int tmp = res[0];
            res[0] = res[1];
            res[1] = tmp;
        }
        return res;
    }

    /**
     * 缺失的第一个正整数（不包括0）
     * @param nums
     * @return
     */
    public int minNumberDisappeared (int[] nums) {

        // 这题暗含技巧：其中未出现的最小整数，如果存在，一定出现在范围[0,nums.length]
        // 为了保证时间复杂度O(N)，这里使用set集合
        Set<Integer> set = new HashSet<>();
        // 遍历插入结果集
        for (int i = 0; i < nums.length; i ++) {
            set.add(nums[i]);
        }
        // 用技巧判断set中是否存在
        for (int i = 1; i <= nums.length; i ++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        // 如果该范围内都存在，那么只能是nums长度+1
        return nums.length + 1;
    }

    /**
     * 三数之和
     * 这一题并没有用到哈希结构
     * 在将三数之和改为两数之和后，是对有序集合采用二分查找的方式寻找的
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // 第一步创建结果集
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (num.length < 3) {
            return res;
        }
        // 第二步排序
        Arrays.sort(num);
        // 第三步三数之后转化为两数字和(i < num.length - 2 保证至少有3个数)
        for (int i =0; i < num.length - 2 ; i ++) {
            // 去重
            if (i != 0 && num[i] == num[i-1]) {
                continue;
            }

            int target = (-1)*num[i];
            int left = i + 1;
            int right = num.length - 1;
            // 寻找两数之和(二分查找)
            while (left < right) {
                if (num[left] + num[right] < target) {
                    left ++;
                } else if (num[left] + num[right] > target) {
                    right --;
                } else {
                    // 找到了
                    ArrayList<Integer> la = new ArrayList<>();
                    la.add(num[i]);
                    la.add(num[left]);
                    la.add(num[right]);
                    // 加入结果集
                    res.add(la);
                    // 去重
                    while (left + 1 < right && num[left] == num[left + 1]) {
                        left ++;
                    }
                    while (left < right - 1 && num[right] == num[right - 1]) {
                        right --;
                    }
                    left ++;
                    right --;
                }
            }
        }

        return res;
    }


    // 坏键盘：一个LinkedHashSet搞定
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.next().toUpperCase();
            String b = in.next().toUpperCase();
            Set<Character> set = new LinkedHashSet<>();
            for (int i = 0; i < a.length(); i ++) {
                if (!b.contains(a.charAt(i)+"")) {
                    set.add(a.charAt(i));
                }
            }
            for (Character ch : set) {
                System.out.print(ch);
            }
        }
    }

    // 前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        // 1、map计数
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {
                map.put(words[i], 1);
            } else {
                map.put(words[i], map.get(words[i]) + 1);
            }
        }
        // 2、优先级队列排序
        PriorityQueue<String> heap = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (map.get(o1) == map.get(o2)) {
                    return o1.compareTo(o2);
                } else {
                    return map.get(o2) - map.get(o1);
                }
            }
        });
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            heap.offer(entry.getKey());
        }

        // 取结果
        List<String> res = new LinkedList<>();
        for (int i = 0;i < k;i ++) {
            res.add(heap.poll());
        }

        return res;

    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    // 随机链表的复制
    public Node copyRandomList(Node head) {
        // 思路：用map将被拷贝节点引用和拷贝节点引用绑定起来，就可以一起操作了
        Map<Node,Node> map = new HashMap<>();

        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        // 重新从头开始遍历，添加指针
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 返回头结点即可
        return map.get(head);

    }

}
